package c_ch11.kruskal;

import java.util.ArrayList;
import java.util.Collections;
import c_ch11.WeightedEdge;

public class Kruskal_try_2020_05_16 {
	
	private ArrayList<WeightedEdge> result = new ArrayList<>(); 

	public Kruskal_try_2020_05_16(String wGraphFile) {

		WeightedGraph_try wg = new WeightedGraph_try(wGraphFile);
		
		ArrayList<WeightedEdge> hub = new ArrayList<>();
		for (int i = 0; i < wg.getV(); i++) {
			for (Integer weightedEdge : wg.adj(i)) {
				//TODO 这里考虑到重复添加了，但不考虑也无妨，因为检测环时会过滤掉，不过这里加上的话，可以大概少循环一半，下边取元素的时候也会少判断将近一半次，下边的快排也会快很多。
				if(i < weightedEdge)//已经保证无自环边
					hub.add(new WeightedEdge(i, weightedEdge, wg.weight(i, weightedEdge)));
			}
		}

		Collections.sort(hub);
		
		UF uf = new UF(wg.getV());
		boolean isNormal = false;
		for (int i = 0; i < hub.size(); i++) {
			WeightedEdge cur = hub.get(i);
			if(uf.isConnected(cur.getV(), cur.getW())) //uf的判断环
				continue;
			
			result.add(cur);
			uf.unionElements(cur.getV(), cur.getW());
			
			if(result.size() == wg.getV()-1) {
				isNormal = true;
				break;
			}
		}
		
		if(!isNormal)
			result.clear();
	}
	
	public ArrayList result() {
		return result;
	}
	
	public static void main(String[] args) {
		System.out.println( new Kruskal_try_2020_05_16("wg.txt").result() );
		System.out.println( new Kruskal_try_2020_05_16("wg2.txt").result() );
	}
}
